import java.util.ArrayList;
import java.util.List;

class Solution3152 {
    public static void main(String[] args) {
        int[]arr = {1,9,7,8,5};
        System.out.println(countSmaller(arr));
    }
    // 临时数组
    static int[] arrX ;// 用来记录元素
    static int[] arrI ; // 用来记录元素的原始下标位置
  static int[] indexs ; // 原始下标
   static List<Integer> sum ;  // 最后返回的就是sum, 记录i外置的元素右边有多少个比他小的元素
    public  static List<Integer> countSmaller(int[] nums) {
         int len = nums.length ;
         sum = new ArrayList<>(len);  // 设置 sum专门用来记录 元素右边有多少个比他小的元素的个数
         indexs = new int[len] ;    // 元素的 原始下标 数组 ;
         for(int i=0 ; i < len ; i++){
              sum.add(0) ; 
              indexs[i] = i ;        // 原始下标
         } 
         arrX = new int[len] ; 
         arrI = new int[len] ; 
         merge(nums , 0 , len-1) ; 
         return sum ;
    }
    private static void merge(int[] nums , int left , int right){
         if(left >= right){ return ;}
         // 划分中间区域
         int mid = left + (right-left)/2 ;
         merge(nums , left , mid) ; 
         merge(nums , mid+1 , right) ; 
         // 遍历数组
         int l = left , r = mid+1 , i = 0 ; 
         while(l <= mid && r <= right){
           // 当左边区间有元素i > 右边区间 元素j时
           if(nums[l] > nums[r]){
             // 首先让 sum里的元素的值++
             // 从原始下标获取下标后,载入 sum里对应位置++ ;
             sum.set(indexs[l] , sum.get(indexs[l])+right-r+1) ;
             // 然后 元素临时数组,放元素
             // 同时 原始下标的临时数组,也跟着移动
             arrX[i] = nums[l] ; 
             arrI[i++] = indexs[l++] ;   // 都放完后才i++ ,l++
           }else{
              arrX[i] = nums[r] ;        //元素和下标一起加到临时数组
              arrI[i++] = indexs[r++] ;    
           }
         }
         while(l <= mid){
            arrX[i] = nums[l] ; 
            arrI[i++] = indexs[l++] ; 
         }
         while(r <= right){
            arrX[i] = nums[r] ; 
            arrI[i++] = indexs[r++];  
         }
         // 把排序后的临时数组的结果 , 覆盖会原数组
         for(int j=left ; j<=right ; j ++){
             nums[j] = arrX[j-left] ; 
             indexs[j] = arrI[j-left];  
         }
    } 
}